package tree;

public class KthSmallestElementInABst230 {
    int val;
    int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root, 0);
        return val;
    }

    private int dfs(TreeNode root, int cur) {
        if (root == null) {
            return cur;
        }
        cur = dfs(root.left, cur);
        if (++cur == k) {
            val = root.val;
        }
        cur = dfs(root.right, cur);
        return cur;
    }

}
